package com.github.yangyishe.p300;

/**
 * 290. 单词规律
 * https://leetcode.cn/problems/word-pattern/?envType=study-plan-v2&envId=top-interview-150
 *
 * 给定一种规律 pattern 和一个字符串 s ，判断 s 是否遵循相同的规律。
 *
 * 这里的 遵循 指完全匹配，例如， pattern 里的每个字母和字符串 s 中的每个非空单词之间存在着双向连接的对应规律。
 *
 *
 *
 * 示例1:
 *
 * 输入: pattern = "abba", s = "dog cat cat dog"
 * 输出: true
 * 示例 2:
 *
 * 输入:pattern = "abba", s = "dog cat cat fish"
 * 输出: false
 * 示例 3:
 *
 * 输入: pattern = "aaaa", s = "dog cat cat dog"
 * 输出: false
 *
 *
 * 提示:
 *
 * 1 <= pattern.length <= 300
 * pattern 只包含小写英文字母
 * 1 <= s.length <= 3000
 * s 只包含小写英文字母和 ' '
 * s 不包含 任何前导或尾随对空格
 * s 中每个单词都被 单个空格 分隔
 */
public class Problem290 {
    public static void main(String[] args) {
        String pattern="abba";
        String s="dog dog dog dog";

        Problem290 problem290 = new Problem290();
        boolean b = problem290.wordPattern(pattern, s);
        System.out.println(b);

    }

    /**
     * 思路:
     * 构建一个类哈希表, 实际是一个长度为26的字符串数组
     * 数组索引对应的是pattern中的字符
     *
     * 遍历s, 每获取到一个字符串, 先根据其位置找到对应的字符(这里可使用双一个指针记录pattern中字符的下标)
     * 再根据字符查找对应的类哈希表中有无有效值.
     *
     * 遍历s时, 获取单词的方式, 可使用快慢指针实现
     * 慢指针指向空格后的第一个下标
     *
     * 容易犯错的实例1:
     * pattern =
     * "abba"
     * s =
     * "dog dog dog dog"
     * 需要在增加哈希表的值时, 保证哈希表的value也都不一致.
     * 可以使用一张新的哈希表, 也可以直接遍历(因为第一张哈希表很小)
     *
     * 易犯错误2:
     * 确保数组下标不越界
     *
     * @param pattern
     * @param s
     * @return
     */
    public boolean wordPattern(String pattern, String s) {
        String[] strings=new String[26];

        int pindex=0;
        int slow=0;
        int fast=0;
        String word;
        while(fast<s.length()){
            char c = s.charAt(fast);
            if(c==' '){
                String findWord=s.substring(slow,fast);
                if(pindex==pattern.length()){
                    return false;
                }
                char pc = pattern.charAt(pindex++);
                if(strings[pc-'a']==null){
                    for(String es:strings){
                        if(es!=null&&es.equals(findWord)){
                            return false;
                        }
                    }
                    strings[pc-'a']=findWord;
                }else if(!strings[pc-'a'].equals(findWord)){
                    return false;
                }
                slow=fast+1;

            }

            fast++;
        }
        String findWord=s.substring(slow,fast);
        if(pindex==pattern.length()){
            return false;
        }
        char pc = pattern.charAt(pindex++);
        if(strings[pc-'a']==null){
            for(String es:strings){
                if(es!=null&&es.equals(findWord)){
                    return false;
                }
            }
            strings[pc-'a']=findWord;
        }else if(!strings[pc-'a'].equals(findWord)){
            return false;
        }


        return pindex==pattern.length();
    }
}
